Side-channel attacks are a class of methods for crypto analysis. In contrast to classical attacks on cryptographic applications, an attacker here does not try to break the underlying abstract mathematical algorithm, but attacks a special implementation of a cryptographic algorithm. In this respect, the attacker uses easily accessible physical measurement variables of the concrete implementation, as for example run-time of the calculation, power consumption and electromagnetic radiation of the processor during the calculation or the behavior of the implementation with induced errors. The physical measurement values of an individual calculation may be analyzed directly (e.g. in a simple power analysis, SPA), or an attacker records measurement values of several calculations (for example using a storage oscilloscope) and evaluates the measurement values subsequently statistically (for example in a differential power analysis, DPA). Side-channel attacks are often substantially more efficient than classical crypto-analytical techniques and may even interfere with methods which are regarded as secure from the point of view of the algorithms when the implementation of this algorithm is not perfected against side-channel attacks. In particular for Smart Cards and embedded applications, countermeasures against side-channel attacks are necessary.
Modern cryptographic systems based on public-key cryptography use physical means, e.g. Smart Cards or dongles to securely store secret key material and to execute asymmetric crypto-operations like digital signatures or the exchange of keys. As a basis for asymmetric cryptography multiplicative groups or elliptic curves may serve. The latter have the advantage that with the same key length the security level is higher, since the best known algorithms for attacking multiplicative groups have sub-exponential running time while only attacks with exponential running time are known for elliptic curve cryptography.
An elliptic curve E is the set of solutions of a cubic equation y2+a1xy+a3y=x3+a2x2+a4x+a6 with coefficients in a finite field K, which has no singular points, i.e. no solutions (r,s) of the equation exist, so that the partial derivations for x and for y of the curve equation have a common zero in (r,s). The solutions to the elliptic curve E together with a point O at infinity as zero element form an additive abelian group whose group law may be interpreted geometrically. Of importance here are two results from algebraic geometry. Each straight line intersects an elliptic curve in three (not necessarily different) points and for two (not necessarily different) points a third point may be calculated, so that the sum of the three points is the neutral element O. Let P and Q be two points on E with P≠−Q and g the straight line through P and Q. (In case P=Q, the straight line is a tangent). This straight line intersects the elliptic curve in a third point R. By mirroring R at the x axis S=P+Q is obtained. The case of P=−Q may be briefly discussed. Then the inclination of a straight line g is infinite and the third intersection is the point O at infinity.
Analogously to the definition of the scalar multiplication in vector spaces, scalar multiplication on elliptic curves is defined. Let P be a point of the elliptic curve E and let k be an integer. The scalar multiplication k*P corresponds to a k-times addition of P to itself. This scalar multiplication forms the substantial element in crypto-systems based on elliptic curves. With cryptographically strong elliptic curves, the scalar multiplication represents a one-way function, i.e. it may be executed in polynomial time, but may only be inverted in exponential time. An efficient algorithmic reconstruction of the scalar thus is already unthinkable with moderate parameter length. With carefully selected cryptographic parameters in practice only unprotected implementations offer possibilities for an attack by analysis of side-channels.
Let (bn-1, . . . , b0) be the binary representation of a scalar k and let P be a point on an elliptic curve. The scalar multiplication Q=k*P may be calculated using the following simple (double-and-add) algorithm:
1) Q←O
2) for i←n−1 to 0 do
3) Q←2*Q
4) if bi=1 then Q←Q+P
5) end
With a simple power analysis attack (SPA) the profile of the power consumption of the hardware during a single scalar multiplication k*P is evaluated. The algorithm of scalar multiplication substantially consists in additions and doublings of points on the elliptic curve. These operations are realized by several mathematical operations in the finite field K and are different, with naive implementation, regarding number and type of the executed operations. Thus, the profile of the power consumption of an addition is different to that of a doubling. These differences may already be made visible with respect to low-cost measurement devices and thus from the sequence of additions and doublings, the binary representation of a scalar may be reconstructed. The scalar here is normally the secret key of a cryptographic protocol to be protected.
With a differential power analysis (DPA) the profiles of the power consumption of the hardware are recorded during several scalar multiplications k*P at different possibly dependently selected inputs using a storage oscilloscope. Subsequently the measurement values are evaluated statistically. In such an attack, typically data locality of key information in cryptographic algorithm is used. The attacker sets up hypotheses over few key bits and tests the correctness of the hypothesis by a classification of the measurement curves and the application of statistical testing methods. The high relevance in danger of DPA on the one hand consists in the fact that the use of many measurement curves may amplify electrical effects which are hidden below the noise threshold of the measurement equipment in individual measurement curves to a level that even individual bits and individual switching operations and changes of states may become visible in the attacked hardware. On the other hand, the technical and financial hurdles for executing such a non-invasive attack are so low that already amateur electronics engineers may be possible attackers. Often only a few hundred measured power profiles are sufficient which may be gathered in a few minutes and a few minutes of calculation time of a script for statistical evaluation in order to attack implementations without suitable countermeasures against side-channel attacks and to completely extract the secret key material stored in the hardware.
A further variant relevant for practice of DPA are template attacks. In this class of attacks initially in a learning phase by means of DPA techniques, the relevant temporal parts of the power profile for the extraction of key data are determined. Here, conventionally, the assumption is made that the attacker has the complete control over the system to be attacked during the learning phase and is in particular able to choose key data. In the second phase of attack key data is extracted from a device with unknown key using these relevant locations with the help of suitable software for post processing. As in the best case for an actual attack only one single profile of the power consumption may be necessary, template attacks may also be regarded as a special case of SPA.
A defense of SPA may be executed by force by adjusting the effort for each bit. This may, on the one hand, be done by an effort adjustment for addition and doubling or by adjusting the sequence of additions and doublings to E. In practice, frequently the second alternative is selected and the algorithm for scalar multiplication is reformulated accordingly.
1) Q0←O
2) for i←n−1 to 0 do
3) Q0←2*Q0 
4) Q1←Q0+P
5) Q0←Qb_i 
6) end
The result of scalar multiplication may be found in the variable Q0. This algorithm results in the fact that the run-time drastically increases and now with each key bit an addition is executed, independent of whether the result of the addition is required for executing the scalar multiplication or not.
A further method for a defense against an SPA attack with respect to a scalar multiplication is represented by the so-called Montgomery Ladder.
Let (bn-1, . . . , b0) be the binary representation of a scalar k and let P be a point on an elliptic curve. The Montgomery Ladder simultaneously calculates the x-coordinates of the points k*P and (k+1)*P. As the x- and y-coordinate of the difference point of the two results are known, the complete point k*P of the result may be reconstructed. The Montgomery algorithm is:
1) R←O, S←P
2) for i←n−1 to 0 do
3) if bi=1 then {R←R+S, S←2*S}
4) else {S←S+R, R←2*R}
5) end
6) reconstruct k*P from R, S and P
The sequence of additions or doublings in step (3) or (4) is now independent of the key bits and completely uniform. Only different jumps in the if-then-else instruction and different addresses for the registers S and R depending on the actual key bit bi generate a variation in the power profile so that the value of the key bits may be computed using this side-channel information.